//
// Created by laichao on 2021/1/2.
//

#include "WeekSolutions.h"
#include <algorithm>
#include <set>
#include <cmath>

///// ================================== GLOBAL VAR ==================================
// 可忽略误差
static constexpr double EPS = 1e-7;
// 极大值
static constexpr double INFTY = 1e20;

///// ================================== HELP CLASS ==================================
struct Query {
    int id, p, m;

    bool operator<(const Query &t) const {
        return m < t.m;
    }
};

///// ================================== HELP FUNCTIONS ==================================
int getString(string &a, string &b) {
    int x = 0, y = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            if (a[i] == '0') x++;
            else y++;
        }
    }
    if (x != y) return INT16_MAX;
    return x;
}

// 计算字符串的所表示的数值
int getStringNum(string &s) {
    int res = 0;
    for (char c:s) res = res * 10 + c - 'a';
    return res;
}

// 计算从零点开始的分钟数
int getTimeMin(string &s) {
    int hour = 0, min = 0;
    // **** sscanf的使用 ****
    sscanf(s.c_str(), "%d:%d", &hour, &min);
    return hour * 60 + min;
}

bool dfsMatrix(vector<vector<int>> &m1, vector<vector<int>> &m2, int x, int y) {
    m2[x][y] = 0;
    bool res = true;
    if (!m1[x][y]) res = false;
    vector<int> dx{0, 0, -1, 1}, dy{-1, 1, 0, 0};
    for (int i = 0; i < 4; i++) {
        int mX = x + dx[i], mY = y + dy[i];
        if (mX >= 0 && mX < m1.size() && mY >= 0 && mY < m1[0].size() && m2[mX][mY]) {
            if (!dfsMatrix(m1, m2, mX, mY)) res = false;
        }
    }
    return res;
}

vector<vector<int>> rotateMatrix(vector<vector<int>> &m) {
    auto copyM = m;
    int n = m.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0, k = n - 1; j < n; j++, k--) {
            copyM[i][j] = m[k][i];
        }
    }
    return copyM;
}

///// =============================== CLASS Definition ===============================
class SeatManager {
private:
    priority_queue<int, vector<int>, greater<int>> heap;
public:
    SeatManager(int n) {
        for (int i = 1; i <= n; i++) heap.push(i);
    }

    int reserve() {
        int minNum = heap.top();
        heap.pop();
        return minNum;
    }

    void unreserve(int seatNumber) {
        heap.push(seatNumber);
    }
};

///// ================================== CLASS FUNC ==================================
string WeekSolutions::replaceDigits(string s) {
    for (int i = 0; i < s.size(); i += 2) {
        int add = (int) (s[i + 1] - '0');
        s[i + 1] = (char) (s[i] + add);
    }
    return s;
}

int WeekSolutions::maximumElementAfterDecrementingAndRearranging(vector<int> &arr) {
    sort(arr.begin(), arr.end());
    int last = 1;
    for (int i = 1; i < arr.size(); i++) {
        last = min(arr[i], last + 1);   // 保证相邻元素之间差不大于1
    }
    return last;
}

vector<int> WeekSolutions::closestRoom(vector<vector<int>> &rooms, vector<vector<int>> &queries) {
    int n = queries.size();
    vector<Query> q;
    for (int i = 0; i < queries.size(); i++) {
        q.push_back({i, queries[i][0], queries[i][1]});
    }
    sort(q.begin(), q.end());
    sort(rooms.begin(), rooms.end(), [](vector<int> &a, vector<int> &b) {
        return a[1] < b[1];     // 按面积从小到大排序
    });
    const int INF_MAX = 1e9;
    set<int> S{-INF_MAX, INF_MAX};
    vector<int> res(n);
    for (int i = n - 1, j = rooms.size() - 1; i >= 0; i--) {    // 双指针
        while (j >= 0 && rooms[j][1] >= q[i].m) S.insert(rooms[j--][0]);  // 所有满足条件的room_id
        int p = q[i].p, id = q[i].id;
        auto k = S.lower_bound(p);  // 二分查找第一个小于p的位置
        auto u = k;
        --u;
        if (p - *u <= *k - p)res[id] = *u;
        else res[id] = *k;
        if (abs(res[id]) == INF_MAX) res[id] = -1;
    }
    return res;
}

int WeekSolutions::getMinDistance(vector<int> &nums, int target, int start) {
    int res = INT16_MAX;
    for (int i = 0; i < nums.size(); i++) {
        if (target == nums[i]) {
            res = min(res, abs(i - start));
        }
    }
    return res;
}

bool WeekSolutions::splitString(string s) {
    // 暴力枚举法， 使用位运算增加速度
    int n = s.size();
    for (int i = 1; i < (1 << (n - 1)); i++) {
        bool flag = true;
        unsigned long long pre = -1, curr = s[0] - '0';     // 分别存储上一个数和当前数
        // 从前往后依次枚举
        for (int j = 0; j < n - 1; j++) {   // 寻找分割位置，规定在数字右边分割，最后一个数字无法分割
            if ((i >> j) & 1) {     // 如果此位置是1，表示分割线
                if (pre != -1 && curr != pre - 1) {
                    flag = false;
                    break;
                }
                pre = curr;    // 可以分割
                curr = s[j + 1] - '0';
            } else {
                curr = curr * 10 + s[j + 1] - '0';
            }
        }
        if (curr != pre - 1) flag = false;
        if (flag) return true;
    }
    return false;
}

int WeekSolutions::getMinSwaps(string num, int k) {
    string s = num;
    while (k--) next_permutation(s.begin(), s.end());
    int n = s.size();
    vector<int> c(n);
    int cnt[10] = {0};
    for (int i = 0; i < n; i++) {
        int x = num[i] - '0';
        cnt[x]++;
        int y = cnt[x];
        for (int j = 0; j < n; j++) {
            if (s[j] - '0' == x && --y == 0) {
                c[i] = j;
                break;
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (c[i] > c[j]) res++;
        }
    }
    return res;
}

int WeekSolutions::subsetXORSum(vector<int> &nums) {
    //********** 二进制枚举 **********
    // 用一个长度为n的二进制数来表示所有的子集，每一位对应nums每一位取还是不取（二进制1和0）
    // 比如：1010对应的就是nums数组的第一个数和第三个数组成的子集。
    int n = nums.size();
    int res = 0;
    for (int i = 0; i < 1 << n; i++) {  // 总共有(1<<n)种子集情况
        int s = 0;
        for (int j = 0; j < n; j++) {
            if (i >> j & 1) {   // 如果当前位为1，表示当前数被选入子集
                s ^= nums[j];
            }
        }
        res += s;
    }
    return res;
}

int WeekSolutions::minSwaps(string s) {
    int n = s.size();
    string a(n, '0'), b(n, '0');
    for (int i = 1; i < a.size(); i += 2) a[i] = '1';
    for (int i = 0; i < b.size(); i += 2) b[i] = '1';
    int res = min(getString(s, a), getString(s, b));
    if (res == INT32_MAX) return -1;
    return res;
}

bool WeekSolutions::checkZeroOnes(string s) {
    int one = 0, zero = 0;
    for (int i = 0, x = 0, y = 0; i < s.length(); i++) {
        if (s[i] == '0') y++, x = 0;
        else x++, y = 0;
        one = max(x, one);
        zero = max(y, zero);
    }
    return one > zero;
}

int WeekSolutions::minSpeedOnTime(vector<int> &dist, double hour) {
    int n = dist.size();
    long long hr = llround(hour * 100); // 将 hour 乘 100 以转为整数
    // 时间必须大于路段数减1
    if (hr <= (n - 1) * 100) return -1;
    // 使用二分算法
    int l = 1, r = 1e7;
    while (l < r) {
        int mid = l + (r - l) / 2;
        long long t = 0;    // 判断当前时速是否满足时限
        for (int i = 0; i < n - 1; i++) {
            t += (dist[i] - 1) / mid + 1;
        }
        t *= mid;
        t += dist[n - 1];
        if (t * 100 <= hr * mid) r = mid;
        else l = mid + 1;
    }
    return l;
}

int WeekSolutions::countGoodSubstrings(string s) {
    if (s.length() < 3) return 0;
    int res = 0;
    for (int i = 0; i < s.length() - 2; i++) {
        int a = i, b = i + 1, c = i + 2;
        if (s[a] != s[b] && s[b] != s[c] && s[a] != s[c]) res++;
    }
    return res;
}

int WeekSolutions::minPairSum(vector<int> &nums) {
    // 思维比较具有跳跃性
    sort(nums.begin(), nums.end());
    int res = 0;
    for (int i = 0, j = nums.size() - 1; i < j; i++, j--) {
        res = max(res, nums[i] + nums[j]);
    }
    return res;
}

vector<int> WeekSolutions::getBiggestThree(vector<vector<int>> &grid) {
    const int N = 110;
    // 前缀和，便于计算菱形的边长
    vector<vector<int>> s1(N, vector<int>(N, 0)), s2(N, vector<int>(N, 0));
    int n = grid.size(), m = grid[0].size();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1];
            s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1];
        }
    }
    set<int> S; // 存最大的三个菱形
    // 枚举菱形中心
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            S.insert(grid[i - 1][j - 1]);   // 菱形半径为0的情况
            // k表示菱形的半径
            for (int k = 1; k <= i - 1 && k <= n - i && k <= j - 1 && k <= m - j; k++) {
                // 计算菱形边长
                int a = s2[i][j - k] - s2[i - k][j];
                int b = s1[i][j + k] - s1[i - k][j];
                int c = s2[i + k][j] - s2[i][j + k];
                int d = s1[i + k][j] - s1[i][j - k];
                S.insert(a + b + c + d - grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1]);
            }
            while (S.size() > 3) S.erase(S.begin());
        }
    }
    return vector<int>(S.rbegin(), S.rend());
}

int WeekSolutions::minimumXORSum(vector<int> &nums1, vector<int> &nums2) {
    // difficult —— ref by yxc.
    int n = nums1.size(), INF = 1e9;
    vector<int> dpArr(1 << n, INF);
    dpArr[0] = 0;
    for (int i = 1; i < 1 << n; i++) {
        int s = 0;
        for (int j = 0; j < n; j++) {
            if (i >> j & 1) s++;
        }
        for (int j = 0; j < n; j++) {
            if (i >> j & 1) dpArr[i] = min(dpArr[i], dpArr[i - (1 << j)] + (nums2[j] ^ nums1[s - 1]));
        }
    }
    return dpArr[(1 << n) - 1];
}

bool WeekSolutions::isSumEqual(string firstWord, string secondWord, string targetWord) {
    return getStringNum(firstWord) + getStringNum(secondWord) == getStringNum(targetWord);
}

string WeekSolutions::maxValue(string n, int x) {
    int k = 0;
    if (n[0] != '-') {
        while (k < n.size() && n[k] - '0' >= x) k++;
    } else {
        k = 1;
        while (k < n.size() && n[k] - '0' <= x) k++;
    }
    return n.substr(0, k) + to_string(x) + n.substr(k);
}

vector<int> WeekSolutions::assignTasks(vector<int> &servers, vector<int> &tasks) {
    // <服务器权重，服务器id>
    priority_queue<pair<int, int>, vector<pair<int, int>>> serverqu;
    for (int i = 0; i < servers.size(); i++) {
        serverqu.push({servers[i], i});
    }
    // <任务截止时间，服务器id>
    priority_queue<pair<int, int>, vector<pair<int, int>>> taskqu;
    // <任务耗时时间，任务id>
    queue<pair<int, int>> qu;

    int i = 0;
    int m = tasks.size();
    vector<int> res(m, 0);
    while (!qu.empty() || !taskqu.empty() || i < m) {
        if (i < m) {
            qu.push({tasks[i], i});
        }
        while (!taskqu.empty() && taskqu.top().first == i) {
            auto curtask = taskqu.top();
            int id = curtask.second;
            serverqu.push({servers[id], id});
            taskqu.pop();
        }
        while (!serverqu.empty() && !qu.empty()) {
            auto server = serverqu.top();
            serverqu.pop();
            auto curtask = qu.front();
            qu.pop();
            taskqu.push({curtask.first + i, server.second});
            res[curtask.second] = server.second;
        }
        if (i >= m && !taskqu.empty()) {
            i = taskqu.top().first;
        } else {
            i++;
        }
    }
    return res;
}

int WeekSolutions::minSkips(vector<int> &dist, int speed, int hoursBefore) {
    int n = dist.size();
    vector<vector<double>> f(n + 1, vector<double>(n + 1, INFTY));
    f[0][0] = 0.;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j != i) {
                f[i][j] = min(f[i][j], ceil(f[i - 1][j] + (double) dist[i - 1] / speed - EPS));
            }
            if (j != 0) {
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + (double) dist[i - 1] / speed);
            }
        }
    }
    for (int j = 0; j <= n; ++j) {
        if (f[n][j] < hoursBefore + EPS) {
            return j;
        }
    }
    return -1;
}

bool WeekSolutions::findRotation(vector<vector<int>> &mat, vector<vector<int>> &target) {
    for (int i = 0; i < 4; i++) {
        mat = rotateMatrix(mat);
        if (mat == target) return true;
    }
    return false;
}

int WeekSolutions::reductionOperations(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int res = 0;
    for (int i = 1, s = 0; i < nums.size(); i++) {
        if (nums[i] != nums[i - 1]) s++;
        res += s;
    }
    return res;
}

int WeekSolutions::minFlips(string s) {
    int n = s.size();
    vector<int> l[2], r[2];
    l[0] = l[1] = r[0] = r[1] = vector<int>(n);
    for (int i = 0; i < 2; i++) {
        for (int j = 0, c = 0, k = i; j < n; j++, k ^= 1) {
            if (k != s[j] - '0') c++;
            l[i][j] = c;
        }
    }
    for (int i = 0; i < 2; i++) {
        for (int j = n - 1, c = 0, k = i; j >= 0; j--, k ^= 1) {
            if (k != s[j] - '0') c++;
            r[i][j] = c;
        }
    }
    int res = 0;
    if (n % 2 == 0) res = min(l[0][n - 1], l[1][n - 1]);
    else {
        res = min(l[0][n - 1], l[1][n - 1]);
        for (int i = 0; i + 1 < n; i++) {
            res = min(res, l[0][i] + r[1][i + 1]);
            res = min(res, l[1][i] + r[0][i + 1]);
        }
    }
    return res;
}

string WeekSolutions::largestOddNumber(string num) {
    int k = num.size() - 1;
    while (k >= 0 && num[k] % 2 == 0) k--;  // 数值和字符ASCII码的奇偶性一样
    if (k < 0) return "";
    return num.substr(0, k + 1);
}

int WeekSolutions::numberOfRounds(string startTime, string finishTime) {
    int start = getTimeMin(startTime), end = getTimeMin(finishTime);
    if (start > end) end += 24 * 60;    // 延续到了第二天
    start = (start + 14) / 15, end = (end + 14) / 15;       // start上取整, end下取整
    return end - start;
}

int WeekSolutions::countSubIslands(vector<vector<int>> &grid1, vector<vector<int>> &grid2) {
    int res = 0;
    for (int i = 0; i < grid1.size(); i++) {
        for (int j = 0; j < grid1[0].size(); j++) {
            if (grid2[i][j]) {  // 对于grid2中的每一个岛屿验证在grid1中是否被完全包含
                if (dfsMatrix(grid1, grid2, i, j)) res++;
            }
        }
    }
    return res;
}

vector<int> WeekSolutions::buildArray(vector<int> &nums) {
    vector<int> res(nums.size());
    for (int i = 0; i < nums.size(); i++) {
        res[i] = nums[nums[i]];
    }
    return res;
}

string WeekSolutions::makeFancyString(string s) {
    string res;
    for (int i = 0; i < s.length(); i++) {
        int j = i + 1;
        while (j < s.length() && s[i] == s[j]) j++;
        for (int k = 0; k < 2 && k < j - i; k++) res += s[i];
        i = j - 1;
    }
    return res;
}
